package com.example.demo.leetcode.classics150;

import java.util.HashMap;

/**
 * ******************************************************
 *
 * @author liugh9
 * @version 1.0
 * @classname _73从中序与后序遍历序列构造二叉树
 * @description
 * @date 2023/08/01 17:23
 * <p>
 * ******************************************************
 */
public class _73从中序与后序遍历序列构造二叉树 {


    // 存储 inorder 中值到索引的映射
    HashMap<Integer, Integer> valToIndex = new HashMap<>();

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        for (int i = 0; i < inorder.length; i++) {
            valToIndex.put(inorder[i], i);
        }

        // 根据函数定义，用 inorder 和 postorder 构造二叉树
        return build(inorder, 0, inorder.length - 1,
                postorder, 0, postorder.length - 1);
    }

    /**
     * build 函数的定义：
     * 若后序遍历数组为 postorder[preStart..preEnd]，[leftNode,....,rightNode,....,root]
     * 中序遍历数组为 inorder[inStart..inEnd]，[leftNode,....,root,rightNode,....]
     * 构造二叉树，返回该二叉树的根节点
     *
     * @param inorder
     * @param inLeft
     * @param inRight
     * @param postorder
     * @param postLeft
     * @param postRight
     * @return
     */
    private TreeNode build(int[] inorder, int inLeft, int inRight, int[] postorder, int postLeft, int postRight) {
        if (inLeft <= inRight) {
            int rootVal = postorder[postRight];
            TreeNode root = new TreeNode(rootVal);
            // 避免 for 循环寻找 rootVal
            int index = valToIndex.get(rootVal);
            int leftSize = index - inLeft;
            root.left = build(inorder, inLeft, inLeft + leftSize - 1,
                    postorder, postLeft, postLeft + leftSize - 1);

            root.right = build(inorder, inLeft + leftSize + 1, inRight,
                    postorder, postLeft + leftSize, postRight-1);
            return root;
        }
        return null;
    }


   public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
}
